/*
题目: 每个元音包含偶数次的最长子字符串
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。

https://leetcode.cn/problems/find-the-longest-substring-containing-vowels-in-even-counts/
 */
public class FindTheLongestSubstring {
    public int findTheLongestSubstring(String s) {
        //遇到求最长的连续子串使得和为k, 想到 前缀和 加哈希表记录第一次出现某一状态的位置。
        int n = s.length();

        // 各种情况 对应 的第一次出现的 下标
        int[] nums = new int[1 << 5];
        Arrays.fill(nums, -2); // 如果这种状态没有遇到过, 就是 -1
        nums[0] = -1;  // 初始化, 特殊处理整个字符串都满足的情况
        int state = 0; // 从 0 开始始 的状态
        int maxn = 0;
        for (int i = 0; i < n; i ++) {
            char ch = s.charAt(i);
            if (ch == 'a')
                state ^= 1;
            else if (ch == 'e')
                state ^= 1 << 1;
            else if (ch == 'i')
                state ^= 1 << 2;
            else if (ch == 'o')
                state ^= 1 << 3;
            else if (ch == 'u')
                state ^= 1 << 4;

            // 第一次遇到这种状态
            if (nums[state] == -2) {
                nums[state] = i;
            } else {
                // 如果不同下标两种状态都是相同的, 那么中间片段 元音字母的出现次数都是偶数次
                maxn = Math.max(maxn, i - nums[state]);
            }
        }

        return maxn;
    }
}
